1. Field of the Invention
The present invention relates to look-up tables and more particularly to a technique for structuring a look-up table in such a way as to reduce complexity.
2. Description of the Related Art
A look-up table (henceforth called a LUT) is commonly used in digital signal processing to translate an input value into a different output value by using the input value as an index to a pre-stored entry in the table, thereby saving or reducing the need for computation of the output value. The pre-stored entry either provides the required result directly or enables this to be found more easily.
Many systems use coefficients that change in a repeated series of values, or a series of instructions that repeat. For example, audio systems make use of such repeating series in volume ramps i.e. volume settings. In such audio systems, it is necessary to provide a look-up table (LUT) to match the current count (provided by an incremental binary counter) with the corresponding coefficient value, or instruction.
FIG. 1 shows a known counter 10 and LUT 12 as described above, where the repeating sequence is of non-binary length. In this specification, the expression “binary length” refers to a length which is an integer power of two, i.e. 2, 4, 8, and so on. Thus, a “non-binary length” is any other integer value.
An example of where the arrangement of FIG. 1 may be used is in audio applications, in which a volume ramp is applied to an audio sample to change its gain (volume) under control of a count value. Typically, a volume ramp uses a series of six values (each representing a −1dB step in the gain) before repeating. This arises from the fact that a −6dB gain is approximately equivalent to a multiplication by ½. Thus, in the volume ramp application, each increment on the counter will correspond to a multiplication by some factor (F1-F6 below) representing a −1dB step. The first step is simply multiplication by unity (F1 in this case), before the sixth increment corresponds to a multiplication by factor F6 to represent a −5dB step. On the seventh step, the multiplication is again by F1 but with a bit shift (representing multiplication by ½).
Alternatively, the volume ramp may use a series of 12 values (each representing a fractional step of −½dB in the gain) before repeating. It will be appreciated that other fractional dB steps may be employed. The number of values in such a series is denoted “m” below.
Thus, in a volume ramp application using 12 values, each increment on the counter will correspond to a multiplication by some factor (F1-F12) each representing a −½dB step. The first step is simply a multiplication by unity (F1 in this case), before the twelfth increment corresponds to a multiplication by factor F12 to represent a −5.5dB step. On the thirteenth step, the multiplication is again by F1 but with a bit shift (representing the multiplication by ½). See the bracketed values in Table 1 below.
In a LUT as outlined above, the coefficient can be viewed as providing the fine adjustment of the output level with the shift value determining the coarse level. The LUT thus consists of repeating sections in each of which the coefficient cycles though its possible values whilst the shift value stays the same, incrementing by one at each new section.
In a typical application, the coefficient and shift values are obtained from the LUT 12, and by means of the multiplier 14 and bit shifter 16 schematically shown in FIG. 2, applied to an input signal Din. Din may be parallel multi-bit data or series data. The LUT in this case is shown in Table 1.
TABLE 1Standard LUT indexingIndex inIndexLUTCoefficientShiftGain00F1(F1)0 (0)0(0)11F20−1 dB22F30−2 dB33F40−3 dB44F50−4 dB55F60−5 dB66F11−6 dB77F21−7 dB88F31−8 dB99F41−9 dB1010F51−10 dB1111F6(F12)1 (0)−11 dB(−5.5 dB)1212F1(F1)2 (1)−12 dB(−6 dB). . .. . .. . .. . .250250F541251251F6(F12)41252252F1(F1)42 (21)253253F242254254F342255255F442
Thus for a typical 8-bit count there are 256 corresponding combinations of coefficients and shift values which may be applied to the input signal DIN. The LUT is therefore very large as unique coefficient and shift values are required for each of the 256 possible input values.
During the digital circuit design the synthesis (from a hardware description language such as Verilog for example) optimisation size is dependent on the repeat cycle length of the two series (the binary nature of the count and the repeat length m of the coefficients). The synthesis tool looks for patterns in the sequence in order to realize the LUT in digital logic. If the sequence is of non-binary length, e.g. m=6 in the above example, this logic becomes very complicated very quickly in order to translate between the count and the repeating sequence. In this example the sequence repeats every 6*8=48 cycles.